#include "mySearch.h"
#include <iostream>
#include <string>

using namespace std;

SSTable::SSTable()
{
    length = 0;
    origin = nullptr;
}

SSTable::SSTable(int length, int *origin)
{
    this->length = length;
    this->origin = new int[length];
    for (int i = 0; i < length; i++)
    {
        this->origin[i] = origin[i];
    }
}

SSTable::~SSTable()
{
    delete[] origin;
}

int SSTable::getLength()
{
    return length;
}

int *SSTable::getOrigin()
{
    return origin;
}

void SSTable::setLength(int length)
{
    this->length = length;
}

void SSTable::setOrigin(int *origin)
{
    this->origin = origin;
}

int SSTable::binSearch(int val)
{
    int low = 0;
    int high = length - 1;
    int mid = 0;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (val == origin[mid])
        {
            return mid;
        }
        else if (val < origin[mid])
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    return -1;
}

BSTreeNode::BSTreeNode()
{
    data = 0;
    lchild = nullptr;
    rchild = nullptr;
}

BSTreeNode::BSTreeNode(int data)
{
    this->data = data;
    lchild = nullptr;
    rchild = nullptr;
}

BSTreeNode::BSTreeNode(int data, BSTreeNode *lchild, BSTreeNode *rchild)
{
    this->data = data;
    this->lchild = lchild;
    this->rchild = rchild;
}

BSTreeNode::~BSTreeNode()
{
}

int BSTreeNode::getData()
{
    return data;
}

BSTreeNode *BSTreeNode::getLChild()
{
    return lchild;
}

BSTreeNode *BSTreeNode::getRChild()
{
    return rchild;
}

void BSTreeNode::setData(int data)
{
    this->data = data;
}

void BSTreeNode::setLChild(BSTreeNode *lchild)
{
    this->lchild = lchild;
}

void BSTreeNode::setRChild(BSTreeNode *rchild)
{
    this->rchild = rchild;
}

BSTree::BSTree()
{
    num = 0;
    root = nullptr;
}

BSTree::BSTree(int num, int *data)
{
    this->num = num;
    root = nullptr;
    for (int i = 0; i < num; i++)
    {
        addNode(data[i]);
    }
}

BSTree::~BSTree()
{
}

int BSTree::getNum()
{
    return num;
}

BSTreeNode *BSTree::getRoot()
{
    return root;
}

void BSTree::setNum(int num)
{
    this->num = num;
}

void BSTree::setRoot(BSTreeNode *root)
{
    this->root = root;
}

void BSTree::print(BSTreeNode *root, string &result)
{
    if (root)
    {
        result = result + to_string(root->getData());
        result = result + " ";
        print(root->getLChild(), result);
        print(root->getRChild(), result);
    }
}

string BSTree::printTree()
{
    string result = "";
    print(root, result);
    return result;
}

bool BSTree::searchNode(int val)
{
    BSTreeNode *current = root;
    while (current)
    {
        if (current->getData() == val)
        {
            return true;
        }
        else if (current->getData() > val)
        {
            current = current->getLChild();
        }
        else
        {
            current = current->getRChild();
        }
    }
    return false;
}

bool BSTree::addNode(int val)
{
    if (searchNode(val))
    {
        return false;
    }
    BSTreeNode *newnode = new BSTreeNode(val);
    if (!root)
    {
        root = newnode;
    }
    else
    {
        BSTreeNode *current = root;
        BSTreeNode *parent = nullptr;
        while (current)
        {
            parent = current;
            if (val < current->getData())
            {
                current = current->getLChild();
            }
            else
            {
                current = current->getRChild();
            }
        }
        if (val < parent->getData())
        {
            parent->setLChild(newnode);
        }
        else
        {
            parent->setRChild(newnode);
        }
    }
    num++;
    return true;
}

bool BSTree::deleteNode(int val)
{
    BSTreeNode *p = root;
    BSTreeNode *f = nullptr;
    BSTreeNode *q = nullptr;
    while (p)
    {
        if (val == p->getData())
        {
            break;
        }
        f = p;
        if (val < p->getData())
        {
            p = p->getLChild();
        }
        else
        {
            p = p->getRChild();
        }
    }
    if (!p)
    {
        return false;
    }
    q = p;
    if ((p->getLChild()) && (p->getRChild()))
    {
        BSTreeNode *s = p->getLChild();
        q = p;
        while (s->getRChild())
        {
            q = s;
            s = s->getRChild();
        }
        p->setData(s->getData());
        if (q != p)
        {
            q->setRChild(s->getLChild());
        }
        else
        {
            q->setLChild(s->getLChild());
        }
        delete s;
        num--;
        return true;
    }
    else if (p->getLChild())
    {
        q = p;
        p = p->getLChild();
    }
    else if (p->getRChild())
    {
        q = p;
        p = p->getRChild();
    }
    else if ((!p->getLChild()) && (!p->getRChild()))
    {
        q = p;
        p = nullptr;
    }
    if (!f)
    {
        root = p;
    }
    else if (q == f->getLChild())
    {
        f->setLChild(p);
    }
    else if (q == f->getRChild())
    {
        f->setRChild(p);
    }
    delete q;
    num--;
    return true;
}